class Solution {
    /*
        思路1:使用双向队列遍历即可，
        当从左向右遍历：取出队首元素，添加新元素到队尾
          从右向左遍历：取出队尾，添加新元素到对首
        注意：
            （遍历左右子树的顺序）
    */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        boolean flag = false; 
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> q = new LinkedList<>();
        if(root!=null) q.offerLast(root);
        while( !q.isEmpty() ){
            List<Integer> list = new ArrayList<>();
            int len = q.size();
            if(!flag){
                for(int i=1; i<=len; i++){
                    TreeNode tmp = q.pollFirst(); // 取出队首元素
                    list.add(tmp.val);           
                    if( tmp.left!=null )  q.offerLast(tmp.left); // 添加到队尾
                    if( tmp.right!=null ) q.offerLast(tmp.right);
                }
            }else{
                for(int i=1; i<=len; i++){
                    TreeNode tmp = q.pollLast(); // 取出队尾元素
                    list.add(tmp.val);   
                    if( tmp.right!=null ) q.offerFirst(tmp.right);   // 添加到队首
                    if( tmp.left!=null )  q.offerFirst(tmp.left);
                }
            }
            flag = !flag;
            res.add(list);
        }
        return res;
    }
}